package com.test.suan_fa.demo1;

/**
 * @author weizhang240
 * @date 2020/6/17 21:15
 * @desc 字节跳动面试
 * 给一个有序的数组，如何变为平衡搜索二叉树
 */
public class Arr2tree {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        Node tree = sortedArrayToBST(arr);
        System.out.println(tree);
    }

        public static Node sortedArrayToBST(int[] nums) {
            return ToBST(nums,0,nums.length-1);
        }
        public static Node ToBST(int nums[], int left, int right){
            if(left>right)return null;//定义的二分区间为[left,right]，无法进行继续递归，直接退出
            int mid = (int)(left+right)/2;//二分中值
            Node root = new Node(nums[mid]);
            root.left = ToBST(nums,left,mid-1);//注意mid-1 对左半部分进行递归
            root.right = ToBST(nums,mid+1,right);//注意mid+1 对右半部分进行递归
            return root;
        }
}

class Node{
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }
}